Графови

Граф \(G=(V,E)\) се састоји од скупа \(V\) чворова и скупа \(E\) грана. Најчешће грана одговара пару различитих чворова, мада су понекад дозвољене и петље, односно гране које воде од чвора ка њему самом. Граф може бити неусмерен или усмерен. Гране усмереног графа су уређени парови чворова и притом је важан редослед два чвора које повезује грана. Ако се граф представља цртежом, онда се гране усмереног графа цртају као стрелице усмерене од једног чвора (почетка) ка другом чвору (крају гране). Гране неусмереног графа су неуређени парови: оне се цртају као обичне дужи. Неусмерен граф се често представља помоћу усмереног графа који се од полазног добија тако што се свака грана између два различита чвора замени са две гране (по једна у сваком смеру). Неусмерен облик усмереног графа \(G=(V,E)\) је исти граф, без смерова на гранама (тако да су парови чворова у \(E\) неуређени).

Степен \(d(v)\) чвора \(v\) је број грана суседних чвору \(v\) (односно број грана које чвор \(v\) повезују са неким другим чвором). У усмереном графу разликујемо улазни степен чвора \(v\) који је једнак броју грана за које је чвор \(v\) крај, односно излазни степен чвора \(v\) који је једнак броју грана за које је чвор \(v\) почетак.

Пут од чвора \(v_1\) до чвора \(v_k\) је низ чворова \(v_1,v_2,\ldots,v_k\) повезаних гранама \((v_1,v_2),\) \((v_2,v_3),\) \(\ldots,\) \((v_{k-1},v_k)\). Пут је прост, ако се сваки чвор у њему појављује само једном. За чвор \(u\) се каже да је достижан из чвора \(v\) ако постоји пут (усмерен, односно неусмерен, зависно од графа) од чвора \(v\) до чвора \(u\). По дефиницији је чвор \(v\) достижан из \(v\). Циклус је пут чији се први и последњи чвор поклапају. Циклус је прост ако се, сем првог и последњег чвора, ни један други чвор у њему не појављује два пута. За граф се каже да је повезан ако (у његовом неусмереног облику) постоји пут између произвољна два чвора. Шума је граф који (у свом неусмереном облику) не садржи циклусе. Дрво је повезана шума. Коренско дрво је усмерено дрво са једним посебно издвојеним чвором, који се зове корен.

Граф \(G'=(V',E')\) је подграф графа \(G=(V,E)\) ако је \(V'\subseteq V\) и \(E'\subseteq E\). Повезујуће дрво неусмереног графа \(G\) је његов подграф који је дрво и садржи све чворове графа \(G\). Повезујућа шума неусмереног графа \(G\) је његов подграф који је шума и садржи све чворове графа \(G\). Aко неусмерени граф \(G=(V,E)\) није повезан, онда се он може на јединствен начин разложити у скуп повезаних подграфова, који се зову компоненте повезаности графа \(G\).